Many signal processing designs require hardware arithmetic support in the form of dedicated adders, subtracters, and multipliers. These operations generally have to be completed in a specified amount of time and with a minimum of circuitry. Typically, these operations require operands and/or results of several digits (bits, in a binary structure) arranged in monotonically increasing orders of magnitude. A need for such circuits has grown in response to demands of digital signal processing and complex analog-to-digital and digital-to-analog converters. As system requirements become more stringent, the number of digits required for an operation increases accordingly.
There are two standard forms of adders. One is the ripple-carry adder, in which each stage provides a carry bit or digit to the following stage. Thus, each digit of the result is dependent on the results of a computation performed on a lower adjacent digit. In this structure, the Nth digit cannot be calculated until the (N--1)th operation is completed. While this is a very space-efficient approach, with the size of the structure increasing linearly with the number of digits required, the speed at which the calculation can be performed is limited by this restriction and is often unacceptable in high-speed systems with wide data paths. The other standard form is the carry look-ahead adder, which bases its calculation for each digit not on outputs of the previous stages, but on inputs to previous stages. In this type of structure speed is enhanced, since each stage of the adder can perform its calculations simultaneously, without waiting for previous stages to complete; however, each successive stage requires approximately twice the circuitry of that preceding it. The complexity of the structure thus grows exponentially with the number of bits or digits in the data path, and is often unwieldy or completely impractical for large data paths. Further, technological restrictions on gate widths often force a compromise on higher-order stages, limiting operational speed.
It is not uncommon for the above two standard adder forms to be combined into a partial look-ahead adder comprised of N ripple-carry stages of M digits each, the M digits being organized into a traditional look-ahead structure. This has neither the speed of a full look-ahead implementation, nor the space efficiency of a ripple-carry structure, but represents a trade-off between the two.
There is a need for an accumulation apparatus that is more efficient than the combination of the two standard forms, and that simultaneously maintains a relatively low level of hardware complexity.